COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	                        CIS 280 torture no. 2
C00017 ENDMK
C⊗;
                        CIS 280 torture no. 2


Evaluate the following. Write in list-notation wherever possible.
1. cdr[(A B)] 
2. (CAR (QUOTE A))
3. cons[A;(B)]
4. cons[atom[ATOM];eq[EQ;(A)]]
5. list[A;B;C]
6. list[A;()]
7. concat[A;(B,C)]
8. append[(A B C); (1 2)]
9. append[A;()]
10. [eq[A;A]→1; T→2]
11. null[()]
12. λ[[x;y]cadr[y]][cons[A;eq[A;B]];(A .(B . C))]
13. λ[[x;y]cadr[y]][cons[A;eq[A;(B . C)]];(A .(B . C))]

True-false (told you!!)
14. for any LISP computation: car[cons[x;y]] = x.
15. for any LISP computation: car[cons[x;Y]] = x.
16. for any LISP computation: [eq[x;y]→ 1; T → 1] = 1
17. for any LISP computation: atom[atom[cons[A;B]]] = T

Define the following terms. Be concise but be precise.
18. call-by-value




19. compilation




20. hashing function




21. stack





22. access environment




23. binary tree




24. total function




25. property list




26-27. garbage collection
         sweep phase




         mark phase


Fill in the blanks.

28.-33.
In a _________ binding scheme we use a name-value stack  and post the binding of variables
in the stack.  When we want to find the value of a  variable we use a ________ search down
the name stack, looking for an occurrence of the variable name. This scheme loses  when we
want  to  allow  function-valued variables.  In  this  case,  a  stack discipline  is  not
sufficiently  general and  we  segment the  "stack" using  access and  _______ environment
pointers.    An alternative  binding  scheme,  called  __________  binding,  replaces  the
name-value stack  with a single  symbol table. Here  we post the  values of variable  in a
______ -cell.    This  scheme has  an  advantage  in lookup  speed.  Here,  all  atoms are
represented as pointers to their symbol-table entries. This  scheme is effective since the
LISP reader makes sure  that atoms are stored __________.  This scheme also has difficulty
if we wish to use the full generality of functional arguments. 

34.-39.
One of  the  more  powerful programming  techniques  is abstraction.    In  data-structure
programming this is  made manifest by describing structures  as representation independent
as  possible (without losing significant facets of the problem). We  think of structures in
terms of at  least three  operations: ___________, _________,  and ____________.   One the
abstract algorithm is suitably  described then we can think about  representations for the
abstract operations.  When  defining procedures (or functions) in LISP we use a notational
device based on the  _______________ for displaying the formal  parameters (or arguments).
The  typical structure of  a algorithmic definition  in LISP  is a ____________definition.
The body of such a definition is a a conditional expression describing the computations to
be performed depending on the  structure of one or more of the inputs.  One or more of the
tests in  the conditional should involve _________________ to insure that the computations
halt for at least some inputs. 

40.-47.
When  we  come  to   the  implementation  of  LISP's  data  structures   we  must  concoct
representations for S-expressions.  A typical memory layout will contain two storage areas
for components on  LISP's structures.   The __________ area  will contain quantities  like
numbers  and the  print-names for  atoms.   The  other area,  called _______________  will
contain  representations of  _________________.  The  storage management  problems of LISP
tend to become quite complex.  Thus instead of leaving such questions up to the user, LISP
handles its own  storage requirements.  This is done as follows:  all un-used cells in the
two areas of LISP memory are chained  together by their cdr-parts.  (the general  term for
such "LISP-type lists is ___________) Now most of the LISP primitive operations are simply
________-manipulation  operations;  they  make no  demands  on  storage.  However ____  is
different; this operation must effectively create a  new cell.  The new cell is  taken off
the ___________ list.   If this list is  non-empty we win and by jiggling  pointers we can
perform   the  desired  operation.     However  if   the  list  is  empty,   we  call  the
____________________. 

48.-50.
One of the novel features of  LISP is its use of an evaluator or  _____________ as part of
its  running  environment.    Basically, LISP  expressions  which  we  want evaluated  are
represented as data structures and are presented to the evaluator.  The evaluator operates
on  the representation  of the  expression and  finally produces  the answer.   There  are
several  advantages  to this  scheme of  things.   First,  the  evaluation process  can be
described as a LISP function, thus giving a concise and precise  desciption of the meaning
of the  constructs of the language.   Also, since  the evalautor is always  available as a
LISP function,  we can  call it  during a  computation. This  allows us  to generate  data
structures during a  computation and then  cause them to be  evaluated.  This  facility is
quite  useful in  an on-line programming  environment where  we are editing  and debugging
programs (i.e. looking  on them  as data objects)  and finally running  pieces of  program
(i.e.  looking on them as program) Most languages, like ________, supply compilers to take
the  source  language constructs  into machine  language code.    LISP compilers  are also
available.  They  are universally written  in LISP and  then asked to compile  themselves.
This process is called __________________. 


Given the following definition
whotakrok[x] <= [atom[cdr[cons[FOO;x]]]→ cadr[(A B C D F)];
                 T → caddr[(A B C D F)]]

Perform the following computation.   Pick the first letter of your last name  and use that
at the  input to a call  on "whotakrok".  (The  final value is the  lowest grade which the
turkey sitting next to you can receive for 280 (this course, dummy).)



			answers

1.  (B)				10. 1
2.  (CAR (QUOTE A))		11. T
3.  (A B)			12. A
4.  undefined: eq is		13. undefined: eq again
     defined only on		14. false: computation on
     atoms.			     y may be undefined 
5.  (A B C)			15. true
6.  (A())			16. eq is partial
7.  (A B C)			17.T
8.  (A B C 1 2 3)
9.  undefined: A not list.

18. an evaluation  scheme in which the  arguments to a  function call are to  be evaluated
before being applied to the function. 

19.  the process of translating  constructs (P1) in  one language into  constructs (P2) in
another language such that the  execution of P1 and the  execution of P2 produce the  same
value  (under appropriate  interpretation).   e.g.  eval [P1]  ≡  execute[P2], where  P2  =
compile[P1], and ≡ involves interpreting the final state of eval and execute. 

20. Given an atom(symbol , identifier, ...) the hashing function will tell which partition
of the symbol table  we should examine to locate  that atom. Hashing is a  fast, efficient
way to search  and store in symbol tables. The hashing function  should be fast and should
result in an even distribution between the partitions (or buckets). When two atoms hash to
the same bucket,  this is called collision.   Collisions can be resolved  by hashing again
(with a different scheme obviously), linear search, etc... 

21. stack is a data structure: an object with constructors, selectors, recoginzers,..  Its
characteristics are such that  we may only  access the last element  placed in the  stack.
Typical implementation is ... . Typical application is to support recursion.  The name has
been  much misused; things  which aren't really  stacks, like spaghetti  stacks have taken
over the name. 

22.the access environment refers to the chain of symbol tables which are accessible during
the evaluation  of an expression.  variable lookup procedes  from the local  table, up the
access chain. 

23. a  binary tree  is a  graph structure  such  that at  any node  there are  either  two
branches(leading away)  or no  branches( terminal nodes).   To  be a  tree, we require  no
intersections in the graph. 

24. a  function is total over a specified domain, when  it is defined for every element of
that domain. Thus over the domain of s-expressions, atom is total, but eq is not. 

25. a property list is a symbol-table entry in LISP. It is a list of attributes and values
associated with each atom. 

26. The sweep-phase goes (linearly) through  memory, collecting all the unmarked cells and
builds a new available space list. 

27.  The mark-phase traverses  all the active  list-structure, marking each  cell which it
visits. 

28.-33. deep, linear, control, shallow, VALUE, uniquely

34.-39.   constructors,  selectors,   recognizers,   λ-calculus,  recursive,   termination
condition. 

40.-47.  full word space, free  space, dotted pairs,  (singly)linked-lists, pointer, cons,
free space list, garbage collector. 

48.-50. interpreter, Threetran, bootstrapping.